package algorithm.swordoff;

/**
 * 把数字翻译成字符串
 *
 * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
 * 一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 * dp[k] = dp[k-1]+dp[k-2] if ni-2ni-1 can be translated, i.e. 10 <=  ni-2ni-1 <= 25
 *         dp[k-1] else
 *         
 * 当 ni-2ni-1不在[10,25]这个范围应该怎么考虑?
 * 显然 ni-2ni-1只能拆开解读,若如此,ni-2应该和dp[k-2]合并去考虑dp[k-1],也就是上面的else情况
 *
 */

public class SQ46 {

    public int translateNum(int num) {
        int dpk_2 = 1, dpk_1 = 1;

        for (int i = 2; i <= String.valueOf(num).length(); i++) {
            int temp = dpk_1;
            // 到第i个位置时,判断前面两个i-2i-1数字是否可被解析
            dpk_1 = canBeTranslated(String.valueOf(num), i-2) ? dpk_1+dpk_2 : dpk_1;
            dpk_2 = temp;
        }
        return dpk_1;
    }

    private boolean canBeTranslated(String num, int start) {
        int i = Integer.parseInt(num.substring(start, start+2));
        return i >= 10 && i <= 25;
    }

    public static void main(String[] args) {
        SQ46 sq46 = new SQ46();
        System.out.println(sq46.translateNum(10));
        System.out.println(sq46.translateNum(9));
        System.out.println(sq46.translateNum(21));
        System.out.println(sq46.translateNum(27));

        // System.out.println(sq46.canBeTranslated(12345, 1));
    }
}
